class Solution {
    //一、斐波那契数列模型
    //第n个泰波那契数
    public int tribonacci(int n) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;
       //创建dp表
       int[] dp = new int[n+1];
       dp[0] = 0;
       dp[1] = dp[2] = 1;
       for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2] + dp[i - 3];
       }
       return dp[n];
    }
    //三步问题
    public int waysToStep(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        if(n == 4) return 4;
        //创建dp表
        int[] dp = new int[n+1];
        //初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        //填表
        for(int i = 4; i <= n; i++){
            dp[i] = ((dp[i-1] + dp[i-2]) % 1000000007 + dp[i-3]) % 1000000007;
        }
        //返回
        return dp[n];
    }
    //最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        //创建dp表
        int[] dp = new int[n + 1];
        //填表
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        //返回
        return dp[n];
    }
    //解码方法
    public static int numDecodings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        //创建dp表
        int[] dp = new int[n];
        //初始化
        if(s[0] > '0' && s[0] <= '9') dp[0] = 1;
        if(n == 1) return dp[0];
        if(s[1] > '0' && s[1] <= '9') dp[1] = dp[0];
        int k = (s[0] - '0') * 10 + (s[1] - '0');
        if(k >= 10 && k <= 26) dp[1] += 1;
        //填表
        for(int i = 2; i < n; i++){
            int num = s[i] - '0';
            if(num > 0 && num <= 9) dp[i] += dp[i-1];
            num = (s[i-1] - '0') * 10 + s[i] - '0';
            if(num >= 10 && num <= 26) dp[i] += dp[i-2];
        }
        //返回
        return dp[n-1];
    }
    //二、路径问题

    public static void main(String[] args) {
        numDecodings("226");
    }
}